class ListNode {
     int val;
     ListNode next;
     ListNode(int x) { val = x; }
 }




public class IsPalindrome {
    public boolean isPalindrome(ListNode head) {
        //处理空链表和单一节点链表情况
        if (head == null || head.next == null) {
            return true;
        }
        //寻找中间节点
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode pre = slow;
        ListNode cur = pre.next;
        if (cur == null) {
            pre.next = head;
        } else {
            ListNode suc = cur.next;
            while (suc != null) {
                cur.next = pre;
                pre = cur;
                cur = suc;
                suc = suc.next;
            }
            cur.next = pre;
        }
        if (cur == null) {
            if(head.val==cur.val){
                return true;
            }
            else return false;
        } else {
            while (head != cur) {
                if (head.val != cur.val) {
                    return false;
                }
                if (head.next == cur) {
                    return true;
                }
                head = head.next;
                cur = cur.next;
            }
            return true;
        }
    }
}